package com.gxc.tree;

import java.util.Scanner;
import java.util.Stack;

/**
 * 根据给定的二叉树结构描述字符串，输出该二叉树按照中序遍历结果字符串。中序遍历顺序为：左子树，根结点，右子树。
 *
 * 输入描述
 * 由大小写字母、左右大括号、逗号组成的字符串:字母代表一个节点值，左右括号内包含该节点的子节点。
 *
 * 左右子节点使用逗号分隔，逗号前为空则表示左子节点为空，没有逗号则表示右子节点为空。
 *
 * 二叉树节点数最大不超过100。
 *
 * 注:输入字符串格式是正确的，无需考虑格式错误的情况。
 *
 * 输出描述
 * 输出一个字符串为二叉树中序遍历各节点值的拼接结果。
 */
public class GenerateTree2 {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String str = scanner.nextLine();
        scanner.close();

        Stack<TreeNode> stack = new Stack<>();
        Stack<Integer> stackSize = new Stack<>();
        TreeNode root = null;
        for (int i = 0; i < str.length(); i++) {
            char c = str.charAt(i);
            if (c == '{') {
                stackSize.push(stack.size());
            } else if (c == '}') {
                if (stackSize.peek() + 1 == stack.size()) {
                    stack.push(null);
                }
                stackSize.pop();
                TreeNode right = stack.pop();
                TreeNode left = stack.pop();
                stack.peek().left = left;
                stack.peek().right = right;
            } else if (c == ','){
                // 若父节点缺少左子树，手动补上 `null`
                if (stackSize.peek() == stack.size()) {
                    stack.push(null);
                }
            } else {
                TreeNode node = new TreeNode(c);
                stack.push(node);
                if(root == null) root = node;
            }
        }

        inOrder(root);
    }

    private static void inOrder(TreeNode node) {
        if (node == null) return;
        inOrder(node.left);
        System.out.print(node.val);
        inOrder(node.right);
    }

    static class TreeNode {
        char val;  // 节点的值
        TreeNode left;  // 左子节点
        TreeNode right; // 右子节点

        TreeNode(char c) {
            this.val = c;
            this.left = null;
            this.right = null;
        }
    }
}
